package leetcode.search;

import java.util.Scanner;

/**
 * 题目：给定的一个二维网格的地图（’1’（陆地）和0（水）），计数岛的数量。岛屿是四面环水，是由相邻的陆地水平或垂直连接而形成的。
 * 你可以假设该网格的所有四个边都被水包围。 采用深度优先遍历，把访问过的改为‘0’，继续遍历
 *
 * @author WangSai
 *
 */
public class IsLandNum {

    // DFS处理二维数组
    public static int numIslands(char[][] matrix) {
        // 异常值检测
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        // 获取矩阵的行列数量
        int rows = matrix.length;
        int cols = matrix[0].length;
        int count = 0;
        // 遍历矩阵的每一个点
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++)
                // 注意char
                if (matrix[i][j] == '1') {
                    count++;
                    dfsSearch(matrix, i, j, rows, cols);
                }
        }
        return count;
    }

    // 每遇到'1'后, 开始向四个方向 递归搜索. 搜到后变为'0',
    // 因为相邻的属于一个island. 然后开始继续找下一个'1'.
    private static void dfsSearch(char[][] matrix, int rowNum, int colNum, int rows, int cols) {
        if (rowNum < 0 || rowNum >= rows || colNum < 0 || colNum >= cols)
            return;
        if (matrix[rowNum][colNum] != '1')
            return;
        matrix[rowNum][colNum] = '0';
        dfsSearch(matrix, rowNum + 1, colNum, rows, cols);
        dfsSearch(matrix, rowNum - 1, colNum, rows, cols);
        dfsSearch(matrix, rowNum, colNum + 1, rows, cols);
        dfsSearch(matrix, rowNum, colNum - 1, rows, cols);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 获取键盘输入的第一行 n 和m 值
        /*String str = sc.nextLine();
        String[] mystr = str.split(" ");*/
        // 行
        int n = 0;
        // 列
        int m = 0;
        // 若存在多个空格，使用split(" "),会出现空字符串现象。下面这么做是为了避免这种情况
        /*for (int i = 0; i < mystr.length; i++) {
            if (mystr[i] != "" && n == 0)
                n = Integer.parseInt(mystr[i]);
            else if (mystr[i] != "" && n != 0)
                m = Integer.parseInt(mystr[i]);
        }*/
        n = 4;
        m = 5;
        // 创建二维数组n行m列，存放矩阵
        char[][] input = new char[n][m];
        char[][] inputCopy = new char[n][m];
        /*int row = 0;
        // 把m行n列矩阵读取到二维数组里面
        while (sc.hasNextLine()) {
            String instr = sc.nextLine();
            input[row] = instr.toCharArray();
            row++;
            if (row == n)
                break;
        }*/
        input[0] = new char[]{'1', '1', '1', '0', '0'};
        input[1] = new char[]{'1', '1', '0', '0', '0'};
        input[2] = new char[]{'0', '0', '1', '0', '0'};
        input[3] = new char[]{'0', '0' ,'0', '1', '1'};
        inputCopy = input;
        int num = numIslands(inputCopy);
        System.out.print(num);
    }
}

